import java.util.HashMap;
import java.util.Random;
import java.util.Set;

/**
 * This class is designed to implement the use of the Finger Table within the Chord
 * structure. The FingerTable is a listing of nodes <i>x</i> distance away from the
 * current node, where <i>x</i> is some multiple of two or the previous node. The 
 * actual address of the node in the format "HostName:port" is stored separately in a 
 * HashMap. 
 *  
 * @author Guillermo Mendez-Kestler
 * @author Patrick Ramsey
 * @version 1.8
 */
public class FingerTable {
	int[] finger;
	HashMap<Integer, String> nodeAddr;
	private static final int RING_SIZE = 16;
	private static final int RING_OVERSIZE = RING_SIZE+2;
	String ourNode;
	int ourHash;
	private static final boolean DEBUG = false;
	
	/**
	 * Constructor to setup a Finger Table, it needs to have the current node Host 
	 * Name and Port number.
	 *  
	 * @param _ourNode The Host Name and port of the node in the form: "HOST:PORT"
	 */
	public FingerTable(String _ourNode) {
		ourNode = _ourNode;
		ourHash = ourNode.hashCode();
		ourHash = ourHash & 0xffff;
		debug("Our New Hash:  " + ourHash);
		finger = new int[RING_OVERSIZE];
		nodeAddr = new HashMap<Integer, String>();
	} // FingerTable constructor
	
	/**
	 * Constructor to setup a Finger Table, it needs to have the current node Host 
	 * Name and Port number.
	 *  
	 * @param _ourHash The Host Name and port of the node in the form: "HOST:PORT" 
	 * hashed. 
	 */
	public FingerTable(int _ourHash) {
		ourHash = _ourHash & 0xffff;
		debug("Our New Hash:  " + ourHash);
		finger = new int[RING_OVERSIZE];
		nodeAddr = new HashMap<Integer, String>();
	} // FingerTable constructor
	
	/**
	 * Adds the hash code of a node, with hash code <i>x</i>, 
	 * to the Finger Table updating the table as necessary. Updating the table: <br>
	 * 		&nbsp;&nbsp;&nbsp;&nbsp;if <i>x</i> is between node a and node b and less 
	 * 		than the current finger node, x is the new finger location<br>
	 * 		&nbsp;&nbsp;&nbsp;&nbsp;else if <i>x</i> is x is greater than equal to the
	 * 		previous finger node, do nothing.<br><br>
	 * Also if there are "empty" nodes greater than us those fingers are updated.
	 * 
	 * @param addr Adds the node, with hash code of <i>addr</i>, to the Finger Table
	 */
	public void add(String addr){
		// Computes the hash code and adds our hash
		int x = addr.hashCode() + ourHash;
		x = x & 0xffff;
		debug("new hash of node (add): "+x);
		debug("adding: (" + x +", " + addr + ")");
		nodeAddr.put(x, addr);
		// checks for successor
		if (x<finger[1] || finger[1]==0) finger[1] = x;
		
		int aftFing=0; // for updating nodes on the finger table
		// adds the node to the correct finger location
		for (int i=0; i<RING_OVERSIZE;i++) {
			int twoI = (int) Math.pow(2, i) + ourHash;
			int twoII = (int) Math.pow(2, i+1) + ourHash;
			if (x>=twoI && x<twoII){
				if (x<finger[i+1] || finger[i+1]==0){
					finger[i+1]=x;
					aftFing = i+1;
				}
				// need to run back and check for previous nodes
				else if (runBack(i+1)){ 
					finger[i+1]=x;
					aftFing = i+1;
				}
				else if (x>=finger[i+1]) break;
			}
		}
		// makes sure there are no empty nodes
		if (aftFing!=0){
			for (; aftFing<RING_OVERSIZE;aftFing++){
				if (finger[aftFing]==0 || finger[aftFing]<x) 
					finger[aftFing]=x;
			}
		}
	} // add(String addr)
	
	/**
	 * Looks backward in the finger table to see if there is a common number
	 *   infesting the finger. 
	 * 
	 * @param spot The point in which we start looking backwards
	 * @return True if there is a number that is the same, False otherwise 
	 */
	private boolean runBack(int spot){
		for (int i=1;i<spot;i++){
			if (finger[spot]==finger[spot-i]) return true;
		}
		return false;
	} // runBack(int)
	
	/**
	 * Removes the hash code of a node, with hash code <i>x</i>, 
	 * from the Finger Table updating the table as necessary.
	 * 
	 * @param addr Removes the node, with hash code <i>x</i>, from the Finger Table
	 */
	public void remove(String addr) {
		int x = addr.hashCode() + ourHash;
		x = x & 0xffff;
		debug("new hash of node (remove): "+x);
		nodeAddr.remove(x);
		// checks to make sure x is in the FingerTable
		boolean inFing = false;
		for (int in : finger){
			if (in==x) inFing = true;
		}
		// If x is in the Finger remove and update
		if (inFing){
			if (finger[0]==x){
				// removing predecessor
				/** DOESNT WORK YET **/
			}else if (finger[1]==x){
				// removing successor
				int temp = 1;
				// find 2nd successor or greater that isn't equal to successor
				while (finger[temp]==x) temp++;
				// update successors so it is not equal to original successor
				for (int tmp=1;tmp<temp;tmp++) finger[tmp] = finger[temp];
			} else {
				// removing 2nd successor or greater
				for (int i=2; i<finger.length;i++){
					if (finger[i]==x){
						finger[i]=finger[i-1];
					}
				}
			}
		} else System.out.println("Cannot remove non-existant node");
	} // remove(String addr)
	
	/**
	 * Removes the hash code of a node, with hash code <i>x</i>, 
	 * from the Finger Table updating the table as necessary.
	 * 
	 * @param x Removes the node, with hash code <i>x</i>, from the Finger Table
	 */
	public void remove(int x) {
		x += ourHash;
		x = x & 0xffff;
		debug("new hash of node (remove): "+x);
		nodeAddr.remove(x);
		// checks to make sure x is in the FingerTable
		boolean inFing = false;
		for (int in : finger){
			if (in==x) inFing = true;
		}
		// If x is in the Finger remove and update
		if (inFing){
			if (finger[0]==x){
				// removing predecessor
				/** DOESNT WORK YET **/
			}else if (finger[1]==x){
				// removing successor
				int temp = 1;
				// find 2nd successor or greater that isn't equal to successor
				while (finger[temp]==x) temp++;
				// update successors so it is not equal to original successor
				for (int tmp=1;tmp<temp;tmp++) finger[tmp] = finger[temp];
			} else {
				// removing 2nd successor or greater
				for (int i=2; i<finger.length;i++){
					if (finger[i]==x){
						finger[i]=finger[i-1];
					}
				}
			}
		} else System.out.println("Cannot remove non-existant node");
	} // remove(int x)
	
	/**
	 * Returns the "HostName:Port" from the address. (It should be what was given)
	 * 
	 * @param addr The address that should be checked
	 * @return The "HostName:Port" of the node 
	 */
	public String get(String addr){
		int x = addr.hashCode() + ourHash;
		x = x & 0xffff;
		debug("new hash of node (get): "+x);
		// for predecessor
		if (x<=0) return nodeAddr.get(finger[0]);
		
		// successor and following
		int ret=0;
		for (int i=0; i<RING_OVERSIZE;i++) {
			int twoI = (int) Math.pow(2, i);
			int twoII = (int) Math.pow(2, i+1);
			if (x>=twoI && x<twoII){
				ret = i+1;
			}
		}
		return nodeAddr.get(finger[ret]);
	} // get(String addr)
	
	/**
	 * Returns the "HostName:Port" of the node with a hash code of <i>x</i>. 
	 * 
	 * @param x The hashCode() of the address to be found.  
	 * @return The "HostName:Port" of the node 
	 */
	public String get(int x){
		x += ourHash;
		x = x & 0xffff;
		debug("new hash of node (get): "+x);
		if (x<=0) return nodeAddr.get(finger[0]);
		int ret = 0;
		for (int i=0; i<RING_OVERSIZE;i++) {
			int twoI = (int) Math.pow(2, i);
			int twoII = (int) Math.pow(2, i+1);
			if (x>=twoI && x<twoII){
				ret = i+1;
			}
		}
		return nodeAddr.get(finger[ret]);
	} // get(int x)
	
	/**
	 * Returns a HashMap of a node's finger table. 
	 * 
	 * @return A node's Finger Table
	 */
	public HashMap<Integer, String> getFinger(){
		return nodeAddr;
	} // getFinger()
	
	/**
	 * Copies the given finger into our finger table. This will replace our finger
	 * table
	 * 
	 * @param someFinger
	 */
	public void copyFinger(HashMap<Integer, String> someFinger){
		nodeAddr.putAll(someFinger);
		// update the this finger from the given finger table
		Set<Integer> keys = someFinger.keySet();
		for (int a:keys){
			this.add(get(a));
		}
	} // copyFinger(HashMap)
	
	/**
	 * Testing FingerTable to see if the methods work correctly
	 * 
	 * @param args None.
	 */
	public static void main(String[] args){
		FingerTable fing = new FingerTable("myHost:5699");
		String other = "someOtherHost:3739";
		System.out.println("Adding: \t\"" + other + "\"");
		fing.add(other);
		arrays(fing);
		
		String num2 = "someHost:";
		Random rand = new Random();
		for (int i =0; i<100; i++ ){
			fing.add(num2 + rand.nextInt(99999));
		}
		
		arrays(fing);
		System.out.println("Getting:\t\"" + fing.get(other) + "\"");
		arrays(fing);
		System.out.println("Removing:\t\"" + other + "\"");
		fing.remove(other);
		arrays(fing);
	}
	
	/**
	 * Prints out the debugging message. 
	 * 
	 * @param msg The message to be printed during debugging
	 */
	private void debug(String msg) {
		if (DEBUG) System.out.println(msg);
	} // debug(String)
	
	/**
	 * Prints the list of powers of two and the given finger table
	 * 
	 * @param fing The finger table to be printed off
	 */
	public static void arrays(FingerTable fing){
		// PRINTS THE ARRAY FOR POWERS OF 2
		System.out.print("pow^2: [00000, ");
		for (int i=0;i<fing.finger.length-1;i++){
			System.out.printf("%05d", (int) Math.pow(2, i));
			System.out.print(", ");
		}
		System.out.println("]");
		
		// PRINTS THE FINGER TABLE
		System.out.print("Array: [");
		for(int a : fing.finger){
			System.out.printf("%05d", a);
			System.out.print(", ");
		}
		System.out.println("]");
	} // arrays(FingerTable)
} // class